package com.wen.Part6.GraphAlgorithm.impl;

import com.wen.Part6.DataStructure.Edge;
import com.wen.Part6.DataStructure.Graph;
import com.wen.Part6.GraphAlgorithm.GraphAlgorithm;

import java.util.Arrays;
import java.util.List;

// 关键路径
public class KeyPath implements GraphAlgorithm {
    @Override
    public Object solve(Graph g) {

        int[] ve = new int[g.getSize()];
        int[] vl = new int[g.getSize()];
        int[] e = new int[g.getEdgeSize()];
        int[] l = new int[g.getEdgeSize()];
        int size = g.getSize();

        for (int i = 0; i < size; i++) {
            ve[i] = 0;
            vl[i] = Integer.MAX_VALUE;
        }

        // 入度的数组
        int[] inDegreeArray = g.getInDegreeArray();
        int[] outDegreeArray = g.getOutDegreeArray();

        int[] visited1 = new int[size];
        int[] visited2 = new int[size];
        int[] stack1 = new int[size];
        int[] stack2 = new int[size];
        int top1 = 0;
        int top2 = 0;

        // 把入度为0的点加入栈中
        for (int i = 0; i < size; i++) {
            if (inDegreeArray[i] == 0){
                stack1[top1++] = i;
            }
            if (outDegreeArray[i] == 0){
                stack2[top2++] = i;
            }
        }
        while(top1 != 0){
            // 入度为0点出栈，访问标记
            int i = stack1[--top1];
            visited1[i] = 1;
//            System.out.println(g.index2Key(i));
            for (Integer k : g.getAccessible(i)) {
                inDegreeArray[k]--;
                ve[k] = Integer.max(ve[k],ve[i]+g.getWeight(i,k));
                if (inDegreeArray[k] == 0 && visited1[k] == 0){
                    stack1[top1++] = k;
                }
            }
        }

        vl[size-1] = ve[size-1];

        while(top2 != 0){
            // 出度为0点出栈，访问标记
            int i = stack2[--top2];
            visited2[i] = 1;

            for (Integer k : g.getAccessibled(i)) {
                outDegreeArray[k]--;
                vl[k] = Integer.min(vl[k],vl[i]-g.getWeight(k,i));
                if (outDegreeArray[k] == 0 && visited2[k] == 0){
                    stack2[top2++] = k;
                }
            }
        }

        // 获取所有边
        List<Edge> edges = g.getEdges();
        for (Edge edge : edges) {
            e[edge.getIndex()] = ve[g.key2Index(edge.getStartKey())];
            l[edge.getIndex()] = vl[g.key2Index(edge.getEndKey())] - edge.getValue();
        }
        for (int i = 0; i < size; i++) {
            System.out.print(g.index2Key(i) + " ");
        }
        System.out.println();
        System.out.println(Arrays.toString(ve));
        System.out.println(Arrays.toString(vl));
        System.out.println(Arrays.toString(e));
        System.out.println(Arrays.toString(l));
        System.out.println("关键事件");
        for (int i = 0; i < size; i++) {
            if (ve[i] == vl[i]){
                System.out.print(g.index2Key(i) + " ");
            }
        }
        System.out.println();
        System.out.println("关键活动");
        for (int i = 0; i < g.getEdgeSize(); i++) {
            if (e[i] == l[i]){
                System.out.print(edges.get(i) + " ");
            }
        }
        return null;
    }
}
